/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     struct ListNode *next;

 * };

 */

bool isPalindrome(struct ListNode* head) {

    struct ListNode* slow = head;

    struct ListNode* fast = head;

    struct ListNode* prev = slow;

    while (fast && fast->next)

    {

        prev = slow;

        slow = slow->next;

        fast = fast->next->next;

    }

    prev->next = NULL;

    struct ListNode* mid = slow;

    struct ListNode* prev1 = NULL;

    struct ListNode* next1 = mid;

    struct ListNode* cur = NULL;

    while (next1)

    {

        if (prev1 == NULL)

        {

            cur = prev1 = next1;

            next1 = next1->next;

            prev1->next = NULL;

        }

        else

        {

            cur = next1;

            next1 = next1->next;

            cur->next = prev1;

            prev1 = cur;

        }

    }

    struct ListNode* newhead = head;

    while (newhead)

    {

        if (newhead->val != cur->val)

        {

            return false;

        }

        newhead = newhead->next;

        cur = cur->next;

    }

    return true;

}